User blog:P進大好きbot/New Difference Sequence System
Here is a new difference sequence system, which I came up with today through a greedy trial to imitate Y-sequence system originally created by a Japanese googologist Yukito. Although it expands in a different way from Y-sequence system, it looks not so bad. WARNING: I might update the expansion rule so that it will finally coincide wth that of Y-sequence system. However, since I am satisfied with this method itself, I might not complete the updating. = Convention = For a set \(X\), I denote by \(X^{< \omega}\) the set of arrays of elements of \(X\). I denote by \(\mathbb{N}_+\) the set of positive integers, by \(S \subset \mathbb{N}_+^{< \omega}\) the subset of non-empty sequences whose leftmost entry is \(1\), by \(\leq_{\textrm{lex}}\) the lexicographic order on \(\mathbb{N}_+^{\omega}\), and by \(<_{\textrm{lex}}\) the strict total order associated to \(\leq_{\textrm{lex}}\). For an array \(a\), I denote by \(\textrm{Lng}(a)\) the length of \(a\). For an array \(a\) and an \(i \in \mathbb{N}\) smaller than \(\textrm{Lng}(a)\), I denote by \(a_i\) the \((1+i)\)-th entry of \(a\). An initial segment of an array \(a\) is an array of the form \((a_i)_{i=0}^{j-1}\) for some \(j \in \mathbb{N}\) smaller than \(\textrm{Lng}(a)-1\). In particular, the empty array is an initial segment of any array. For arrays \(a\) and \(b\), I denote by \(a \frown b\) the concatenation of \(a\) and \(b\). = Difference Sequence = I denote by \begin{eqnarray*} \textrm{Parent} \colon \mathbb{N}^{< \omega} \times \mathbb{N} \to \mathbb{N} \end{eqnarray*} the partial computable map introduced here. Roughly speaking, \(\textrm{Parent}\) is the function which outputs the index of the parent of the index in the input. Since \(\textrm{Parent}\) forms a bad root searching rule in the sense of the terminology introduced here, it induces the total computable maps \begin{eqnarray*} \begin{array}{lcrcl} \textrm{Ancestor} & \colon & \mathbb{N}^{< \omega} & \to & \mathbb{N}^{< \omega} \\ \textrm{RightNodes} & \colon & \mathbb{N}^{< \omega} & \to & \mathbb{N}^{< \omega} \\ \textrm{Kaiser} & \colon & \mathbb{N}^{< \omega} \setminus \{()\} & \to & \mathbb{N}^{< \omega} \end{array} \end{eqnarray*} introduced in the same article. Roughly speaking, \(\textrm{Ancestor}\) is the function which outputs the sequence of indices of ancestors of the rightmost entry of the input, \(\textrm{RightNodes}\) of the function which outputs the sequence of entries of ancestors of the rightmost entry of the input, \(\textrm{Kaiser}\) is the function which outputs the difference sequence of the value of \(\textrm{RightNodes}\). I define total computable maps \begin{eqnarray*} \begin{array}{lcrcl} \textrm{Royal} & \colon & \mathbb{N}_+^{< \omega} \times \mathbb{N}_+^{< \omega} & \to & \mathbb{N}_+^{< \omega} \\ & & (a,b) & \mapsto & \textrm{Royal}(a,b) \\ \textrm{Prince} & \colon & \mathbb{N}_+^{< \omega} & \to & \mathbb{N}_+^{< \omega} \\ & & b & \mapsto & \textrm{Prince}(b) \end{array} \end{eqnarray*} simultaneously in the following recursive way: # Suppose \(\textrm{Lng}(\textrm{Ancestor}(b)) \leq 1\). ## Set \(\textrm{Royal}(a,b) := a \frown b\). ## Set \(\textrm{Prince}(b) := b\). # Suppose \(\textrm{Lng}(\textrm{Ancestor}(b)) > 1\) and \(\textrm{Ancestor}(b)_0 = 0\). ## Put \(i := \textrm{Ancestor}(\textrm{Kaiser}(b))_0\). ## Suppose \(\textrm{RightNodes}(\textrm{Kaiser}(b))_0 = 1\). ### \(\textrm{Royal}(a,b)\) is the rightmost entry of \(\textrm{Principal}(\textrm{Kaiser}(b))\). ### \(\textrm{Prince}(b)\) is the sequence given by removing the first \(\textrm{Ancestor}(b)_i\) entries from \(b\). ## Suppose \(\textrm{RightNodes}(\textrm{Kaiser}(b))_0 > 1\). ### Denote by \(c\) the initial segment of \(b\) of length \(\textrm{Ancestor}(b)_i+1\). ### Denote by \(d\) the rightmost entry of \(\textrm{Principal}(\textrm{Kaiser}(b))\). ### Set \(\textrm{Royal}(a,b) := \textrm{Royal}(a \frown c,d)\). ### Set \(\textrm{Prince}(b) := \textrm{Prince}(\textrm{Royal}(a,b))\). # Suppose \(\textrm{Lng}(\textrm{Ancestor}(b)) > 1\) and \(\textrm{Ancestor}(b)_0 \neq 0\). ## Denote by \(c\) the initial segment of \(b\) of length \(\textrm{Ancestor}(b)_0\). ## Denote by \(d\) the rightmost entry of \(\textrm{Principal}(b)\). ## Set \(\textrm{Royal}(a,b) := \textrm{Royal}(a \frown c,d)\). ## Set \(\textrm{Prince}(b) := \textrm{Prince}(d)\). These maps imitate the bad root searching rule in Y-sequence system. = Constructibility = A sequence \(a\) is said to be additive principal if \(\textrm{Ancestor}(a)_0 = 0\), and is said to be a decreasing sum if \(a\) can be expressed as a concatenation of an \(A \in \mathbb{N}_+^{< \omega}\) satisfying that \(A_i\) is additive principal for any \(i \in \mathbb{N}\) smaller than \(N\) and \(A_{i+1} \leq_{\textrm{lex}} A_i\) for any \(i \in \mathbb{N}\) smaller than \(N-1\). If \(a\) is a decreasing sum, such an \(A\) is unique, and will be denoted by \(\textrm{Principal}(a)\). I define a total computable map \begin{eqnarray*} \textrm{Shape} \colon \mathbb{N}_+^{< \omega} & \to & \mathbb{N}_+^{< \omega} \\ a & \mapsto & \textrm{Shape}(a) \\ \end{eqnarray*} in the following recursive way: # Put \(L := \textrm{Lng}(b)\). # For each \(i \in \mathbb{N}\) smaller smaller \(N\), define a \(b_i \in \mathbb{N}\) in the following recursive way: ## Suppose \((a,i) \in \textrm{dom}(\textrm{Parent})\). ### Put \(j := \textrm{Parent}(a,i)\). ### Set \(b_i := b_j+1\). ## If \((a,i) \notin \textrm{dom}(\textrm{Parent})\), then set \(b_i := 1\). # Set \(\textrm{Shape}(a) := (b_i)_{i=0}^{L-1}\). Roughly speaking, \(\textrm{Shape}\) is the function which outputs the shape of hydra associated to the input. I define a recursive subset \(T \subset \mathbb{N}_+^{< \omega}\) in the following recursive way: # For any \(i \in \mathbb{N}_+\), \((i) \in T\). # For any decreasing sum sequence \(a\), if \(a\) is not additive principal and \(\textrm{Principal}(a) \in T^{< \omega}\), then \(a \in T\). # For any additive principal sequence \(a\), if \(a = (i) \frown b\) for some \((i,b) \in \mathbb{N}_+ \times T\), \(\textrm{Kaiser}(a) \in T\), and \(\textrm{Shape}(\textrm{Prince}(a)) \leq_{\textrm{lex}} \textrm{Shape}(a)\), then \(a \in T\). The set \(T\) is an analogue of the set of Cantor normal forms, but reflects the shapes of the difference sequences. I define a total computable map \begin{eqnarray*} \textrm{IsConstructibleFromBelow} \colon S \times S & \to & \{0,1\} \\ (a,b) & \mapsto & \textrm{IsConstructibleFromBelow}(a,b) \end{eqnarray*} in the following recursive way: # If \(a \notin T\), then set \(\textrm{IsConstructibleFromBelow}(a,A) := 0\). # If \(a \in T\) and \(b \leq_{\textrm{lex}} a\), then set \(\textrm{IsConstructibleFromBelow}(a,A) := 0\). # Suppose \(a \in T\) and \(a <_{\textrm{lex}} b\). ## If \(\textrm{Lng}(a) = 1\), then set \(\textrm{IsConstructibleFromBelow}(a,b) := 1\). ## Suppose \(\textrm{Lng}(a) \neq 1\). ### Denote by \(B_0\) by the finite set of sequences which are entries of \(\textrm{Principal}(a)\). ### Denote by \(B_1\) by the finite set of sequences given as non-empty initial segments of some \(b \in B_0\). ### Denote by \(B_2\) by the finite set of sequences of the form \(\textrm{Royal}(b)\) for some \(b \in B_1\). ### Set \(\textrm{IsConstructibleFromBelow}(a,b) := \prod_{b \in B_2} \textrm{IsConstructibleFromBelow}(b,a)\). Namely, \(\textrm{IsConstructibleFromBelow}\) is a function which tells us whether every entry of \(A\) is "constructible" from below \(a\) in some sense. = Expansion = I define a total computable map \begin{eqnarray*} [ \ ] \colon S \times \mathbb{N} & \to & S \\ (a,n) & \mapsto & an \end{eqnarray*} in the following recursive way: ; Definition of \(an\): # If \(a = (1)\), then set \(an := (1)\). # If \(a \neq (1)\), then \(an\) is the maximum with respect to \(\leq_{\textrm{lex}}\) of a \(b \in S\) satisfying \(\textrm{IsConstructibleFromBelow}(b,a) = 1\) and \(\textrm{Lng}(b) \leq \textrm{Lng}(a)-1+n\). Roughly speaking, it is supposed to be as strong as possible following the restriction on the constructibility. = Large Function = I define a partial computable map \begin{eqnarray*} \langle \cdot, \cdot \rangle \colon S^{< \omega} \times \mathbb{N} & \to & \mathbb{N} \\ (A,n) & \mapsto & \langle A, n \rangle \end{eqnarray*} in the following recursive way: # If \(A = ()\), then set \(\langle A, n \rangle := n\). # Suppose \(A = (a)\) for some \(a \in S\). ## If \(a = (1)\), then set \(\langle A, n \rangle := n+1\). ## If \(a \neq (1)\), then set \(\langle A, n \rangle := \langle ((\underbrace{an+1,\ldots,an+1}_{n+1}), n+1 \rangle\). # Suppose that the length of \(A\) is greater than \(1\). ## Denote by \(B\) the array given by removing the rightmost entry from \(A\). ## Denote by \(a\) the rightmost entry of \(A\). ## Set \(\langle A, n \rangle := \langle B, \langle (a), n \rangle \rangle\). This is just a computable variant of FGH. Although I do not know whether it is total or not, \(\langle ((1,10)), 10 \rangle\) will be a computable large number if it actually terminates. = Example = Here is a table of examples of expansions. I emphasise expressions which are known to be non-standard or to expand in a way different from those of Y-sequence system by using \(\color{red}{\textrm{red}}\) symbols. = Relation to Y-Sequence System = Since the examples above of expansions in this notation which are different from those of Y-sequence system are actually greater than those of Y-sequence system with respect to \(\leq_{\textrm{lex}}\), there is no obvious implication from the termination of Y-sequence system to the termination of this system. I guess that the termination of this notation implies the termination of Y-sequence system, because my algorithm gives as strong expansions as possible following the restriction on the constructibility, which Y-sequence system also seem to be following in my guess. Since the behaviour of the reconstruction from the difference sequence does not reflect the parent-child relation of the original sequence, if this notation is not terminating, then the example of an infinite loop which will be discovered first will be perhaps a sequence which is not strictly increasing. I add an explanation of \((1,3,10)\), which is supposed to be non-standard in Y-sequence system but is standard in this system. I have \begin{eqnarray*} & & \textrm{Royal}((),(1,3,10)) = (1,2,5) \\ & & \textrm{Prince}((1,3,10)) = \textrm{Prince}((1,2,5)) = (1,3). \end{eqnarray*} Although \((1,2,5)\) itself is non-standard in this notation, it is constructible below from \((1,3,10)\). Indeed, I have \begin{eqnarray*} & & \textrm{Shape}((1,3,10)) = (1,2,3) \\ & & \textrm{Shape}(\textrm{Prince}((1,3,10))) = \textrm{Shape}((1,3)) = (1,2) \leq_{\textrm{lex}} (1,2,3) \end{eqnarray*} and \begin{eqnarray*} & & \textrm{IsConstructibleBelowFrom}((1,2,5),(1,3,10)) \\ & & = \textrm{IsConstructibleBelowFrom}((1),(1,3,10)) \times \textrm{IsConstructibleBelowFrom}((1,3),(1,3,10)) \\ & & = \textrm{IsConstructibleBelowFrom}((1),(1,3,10))^2 \times \textrm{IsConstructibleBelowFrom}((1,2),(1,3,10)) \\ & & = \textrm{IsConstructibleBelowFrom}((1),(1,3,10))^3 = 1^3 = 1. \end{eqnarray*} That is why \((1,3,10)\) is standard in this notation and appears in the expansion of \((1,4)\). Category:Blog posts